package leetcode.map;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

public class Lc207 {


    public boolean canFinish(int numCourses, int[][] prerequisites) {

        int[] indgree = new int[numCourses];
        List<Integer>[] next = new List[numCourses];
        for (int i = 0; i < prerequisites.length; i++) {
            int a = prerequisites[i][0];
            int b = prerequisites[i][1];
            indgree[a]++;
            List<Integer> list = next[b] == null ? new ArrayList<>() : next[b];
            list.add(a);
            next[b] = list;
        }
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) {
            if (indgree[i] == 0)
                deque.offerLast(i);
        }
        int cnt = 0;
        while (!deque.isEmpty()) {
            int courses = deque.pollFirst();
            cnt++;
            if (next[courses] != null) {
                for (int course : next[courses]) {
                    if (--indgree[course] == 0) {
                        deque.offerLast(course);
                    }
                }
            }
        }
        return cnt == numCourses ? true : false;
    }
}
